
int subarraysDivByK(vector<int>& nums, int k) {
    int sum = 0, count = 0;
    map<int, int> dp;
    dp[0] = 1;
    for (auto ch : nums) {
        sum += ch;
        if (dp.count((sum % k + k) % k)) count += dp[(sum % k + k) % k];
        dp[(sum % k + k) % k]++;
    }
    return count;
}
int mySqrt(int x) {
    if (x < 1)
        return 0;
    long long left = 0, right = x;
    for (; left < right;)
    {
        long long mid = left + (right - left + 1) / 2;
        if (mid * mid <= x) left = mid;
        else right = mid - 1;
    }
    return left;
}
int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    if (nums[left] < target)
        return left + 1;
    return left;

}